package com.list;

/**
 * 双向链表:
 * 每两个元素之间都有相互之间的指向
 * 前一个元素.next = 下一个元素,下一个元素.prev = 上一个元素
 * 但是第一个元素.prev = null ,同理最后一个元素.next = null
 */
public class DoublyLinkedList implements ILinkedList {
    LinkedNode head;    //这里我们将 head 作为所有节点的头,即 head.next 指向第一个元素

    @Override
    //将一个节点插入到开头
    public void insert(int key) {
        LinkedNode node = new LinkedNode(key);
        if (!isEmpty()) {
            node.next = head.next;
            head.next = node;
            node.next.prev = node;
        } else {
            head.next = node;
        }
    }

    @Override
    //将末尾的节点删除
    public int delete() {
        assert !isEmpty();
        LinkedNode p = new LinkedNode(0);
        p.next = head.next;
        while (p.next.next != null) {
            p = p.next;
        }
        //现在 p.next.next 为 null,即 p -> p.next -> null ,现在要删除 p.next
        int key = p.next.key;
        p.next = null;
        return key;
    }

    @Override
    //判空
    public boolean isEmpty() {
        return head.next == null;
    }

    public DoublyLinkedList() {
        head = new LinkedNode(0);
    }

}
